package main

/*
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
*/

import "fmt"

type data struct {
	pos     []int
	pathSum int
}

// 如果使用bfs dfs，选路的策略会影响最后结果
func minPathSumBFS(grid [][]int) int {
	var queue []data
	var visited [][]bool
	for i := 0; i < len(grid); i++ {
		visited = append(visited, make([]bool, len(grid[i])))
	}
	queue = append(queue, data{pos: []int{0, 0}, pathSum: grid[0][0]})
	visited[0][0] = true
	min := 999
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			row := queue[0].pos[0]
			col := queue[0].pos[1]
			tmp := queue[0].pathSum
			queue = queue[1:]
			if row == len(grid)-1 && col == len(grid[0])-1 {
				if tmp < min {
					min = tmp
				}
			}
			if col+1 < len(grid[row]) {
				if !visited[row][col+1] {
					visited[row][col+1] = true
					queue = append(queue, data{pos: []int{row, col + 1}, pathSum: tmp + grid[row][col+1]})
				}
			}
			if row+1 < len(grid) {
				if !visited[row+1][col] {
					visited[row+1][col] = true
					queue = append(queue, data{pos: []int{row + 1, col}, pathSum: tmp + grid[row+1][col]})
				}
			}
		}
	}
	return min
}

func minPathSumDFS(grid [][]int) int {
	var visited [][]bool
	for i := 0; i < len(grid); i++ {
		visited = append(visited, make([]bool, len(grid[i])))
	}
	var min int = 999
	dfs(grid, 0, 0, visited, 0, &min)
	return min
}

func dfs(grid [][]int, row, col int, visited [][]bool, sum int, min *int) {
	visited[row][col] = true
	sum += grid[row][col]
	if row == len(grid)-1 && col == len(grid[0])-1 {
		if sum < *min {
			*min = sum
		}
		return
	}
	if col+1 < len(grid[row]) {
		if !visited[row][col+1] {
			dfs(grid, row, col+1, visited, sum, min)
		}
	}
	if row+1 < len(grid) {
		if !visited[row+1][col] {
			dfs(grid, row+1, col, visited, sum, min)
		}
	}
}

type pos struct {
	x int
	y int
}

func minPathSum(grid [][]int) int {
	var dp [][]int
	var dpPath [][][]pos // 如果同时还需要保存路径
	for i := 0; i < len(grid); i++ {
		dp = append(dp, make([]int, len(grid[i])))
		dpPath = append(dpPath, make([][]pos, len(grid[i])))
	}
	// base case
	dp[0][0] = grid[0][0]
	dpPath[0][0] = append(dpPath[0][0], pos{x: 0, y: 0})
	// 状态转移
	for i := 0; i < len(dp); i++ {
		for j := 0; j < len(dp[i]); j++ {
			if i == 0 && j == 0 {
				continue
			}
			if i == 0 {
				dp[i][j] = dp[i][j-1] + grid[i][j]
				dpPath[i][j] = append(dpPath[i][j-1], pos{i, j})
				continue
			}
			if j == 0 {
				dp[i][j] = dp[i-1][j] + grid[i][j]
				dpPath[i][j] = append(dpPath[i-1][j], pos{i, j})
				continue
			}
			// dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
			if dp[i-1][j] < dp[i][j-1] {
				dp[i][j] = dp[i-1][j] + grid[i][j]
				dpPath[i][j] = append(dpPath[i-1][j], pos{i, j})
				continue
			} else {
				dp[i][j] = dp[i][j-1] + grid[i][j]
				dpPath[i][j] = append(dpPath[i][j-1], pos{i, j})
				continue
			}
		}
	}
	for i := 0; i < len(dpPath); i++ {
		fmt.Println(dpPath[i])
	}
	return dp[len(grid)-1][len(grid[0])-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	grid := [][]int{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}
	// fmt.Println(minPathSumDFS(grid))
	fmt.Println(minPathSum(grid))
}
